#include "stdafx.h"
#include "TrieTree.h"


TrieTree::TrieTree()
{
}


TrieTree::~TrieTree()
{
}

TrieTree::TrieTree(char c)
{
	letterChar = c;
}

char * subString(char * str, int start)
{
	if (str == 0) return 0;
	char c;
	int j = 0;
	for (int i = start; str[i] != '\0'; i++)
	{
		c = str[i];
		str[j] = c;
		j++;
	}
	str[j] = '\0';
	return str;
}

void TrieTree::addLetter(Letter letter, char * spl)
{
	if (0 < strlen(spl))
	{
		char c = spl[0];
		TrieTree* child;
		if ((child = inChildPos(c)) == null)
		{
			child = new TrieTree(c);
			childNodes.add(child);
		}
		spl = subString(spl,1);
		if (strlen(spl) == 0)
		{
			if (!containsLetter(child->letters, letter))
				child->letters.add(letter);
			List<Letter>* pList = child->letters.next;
			while (pList)
			{
				pList = pList->next;
			}
			return;
		}
		child->addLetter(letter, spl);
	}
}

bool TrieTree::containsLetter(List<Letter> letters, Letter letter)
{
	List<Letter> * next = letters.next;
	while (next)
	{
		if (next->data.freq == letter.freq && strcmp(letter.letter, next->data.letter) == 0)
		{
			return true;
		}
		next = next->next;
	}
	return false;
}

TrieTree* TrieTree::getPrefixNode(char * prefix)
{
	if (strlen(prefix) == 0) return this;
	TrieTree* node = inChildPos(prefix[0]);
	if (node == null) return null;
	return node->getPrefixNode(subString(prefix,1));
}

void TrieTree::addLettersToList(List<Letter> *subLetters, int layer, int max)
{
	if (subLetters->size() >= max) return;
	if (layer == 0) return;
	if (letters.size() > 0)
		subLetters->addAllLimit(&letters,max);
	layer--;
	List<TrieTree*>* pList = childNodes.next;
	if (pList == null) return;
	TrieTree* pNode = pList->data;
	while (pList != null && (pNode = pList->data))
	{
		pNode->addLettersToList(subLetters, layer, max);
		pList = pList->next;
	}
}

void TrieTree::getAllSubLetters(List<Letter> *subLetters, char * spl, int layer, int max)
{
	TrieTree* prefixNode = getPrefixNode(spl);
	TrieTree* node = prefixNode;
	if (node != null)
	{
		node->addLettersToList(subLetters, layer, max);
	}
}

TrieTree* TrieTree::inChildPos(char c)
{
	if (childNodes.size() == 0) return null;
	List<TrieTree *>* next = childNodes.next;
	while (next)
	{
		if (next->data->letterChar == c)
			return next->data;
		next = next->next;
	}
	return null;
}

